package org.labuladong.动态规划算法.二维DP;

/**
 * @Auther: qingle
 * @Date: 2024/10/26-20:42
 * @Description:⼀个机器⼈位于⼀个 m x n ⽹格的左上⻆（起始点在下图中标记为 Start）。
 * 机器⼈每次只能向下或者向右移动⼀步。机器⼈试图达到⽹格的右下⻆（在下图中标记为“Finish”）。
 * 问总共有多少条不同的路径？
 *
 * 输⼊：m = 3, n = 7
 * 输出：28
 *
 * 输⼊：m = 3, n = 2
 * 输出：3
 * 解释： 从左上⻆开始，总共有 3 条路径可以到达右下⻆。
 * 1. 向右 -> 向下 -> 向下
 * 2. 向下 -> 向下 -> 向右
 * 3. 向下 -> 向右 -> 向下
 *
 * @version: 1.0
 */
public class LC_62_不同路径 {

	class Solution {
		// 备忘录
		int[][] memo;
		public int uniquePaths(int m, int n) {
			memo = new int[m][n];
			return dp(m - 1, n - 1);
		}
		// 定义：从 (0, 0) 到 (x, y) 有 dp(x, y) 条路径
		int dp(int x, int y) {
			// base case
			if (x == 0 && y == 0) {
				return 1;
			}
			if (x < 0 || y < 0) {
				return 0;
			}
			// 避免冗余计算
			if (memo[x][y] > 0) {
				return memo[x][y];
			}
			// 状态转移⽅程：
			// 到达 (x, y) 的路径数等于到达 (x - 1, y) 和 (x, y - 1) 路径数之和
			memo[x][y] = dp(x - 1, y) + dp(x, y - 1);
			return memo[x][y];
		}

	}

	public static void main(String[] args) {

		System.out.println(new LC_62_不同路径().new Solution().uniquePaths(3,7));
	}


}
